package com.cheung.leetcode.tree;

import lyroot.entity.Node;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.tree
 * @Author :  cheungming
 * @CreateTime : 2024-05-20 10:55:01
 * @Description : 多叉树遍历
 * @Version : 1.0
 */
public class Code429Test {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                if (node == null) {
                    continue;
                }
                temp.add(node.val);
                if (node.children != null && !node.children.isEmpty()) {
                    queue.addAll(node.children);
                }
            }
            res.add(temp);
        }

        return res;
    }

    @Test
    public void test1() {
        Node root = new Node(1);

        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);

        root.children = List.of(node3, node2, node4);
        node3.children = List.of(new Node(5), new Node(6));
        System.out.println("levelOrder(root) = " + levelOrder(root));

        assert List.of(List.of(1), List.of(3, 2, 4), List.of(5, 6)).equals(levelOrder(root));
    }

    @Test
    public void test2() {
        Node root = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        root.children = List.of(node2, node3, node4, node5);

        Node node6 = new Node(6);
        Node node7 = new Node(7);
        node3.children = List.of(node6, node7);

        Node node11 = new Node(11);
        Node node14 = new Node(14);

        node7.children = List.of(node11);
        node11.children = List.of(node14);


        Node node8 = new Node(8);
        Node node12 = new Node(12);
        node4.children = List.of(node8);
        node8.children = List.of(node12);

        Node node9 = new Node(9);
        Node node10 = new Node(10);
        node5.children = List.of(node9, node10);
        node9.children = List.of(new Node(13));

        System.out.println("levelOrder(root) = " + levelOrder(root));

        assert List.of(List.of(1), List.of(2, 3, 4, 5), List.of(6, 7, 8, 9, 10), List.of(11, 12, 13), List.of(14))
                .equals(levelOrder(root));
    }
}
